/*
 * @lc app=leetcode.cn id=297 lang=cpp
 *
 * [63f.] 二叉搜索树的第k个节点
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec
{
 public:
  TreeNode* ans;
  TreeNode* kthNode(TreeNode* root, int k)
  {
    // 简要思想，中序遍历就是递增序列
    // 用一个k--，记录离需要返回kth的距离，当k==0时找到了
    dfs(root, k);
    return ans;
  }

  void dfs(TreeNode* root, int& k)
  {
    if (!root) return;
    // 访问左子树
    dfs(root->left, k);
    // 访问根节点，仅当k==0时取根节点的值
    k--;
    if (!k) ans = root;
    // 访问右子数，剪枝当找到k时，不需要访问右子树了
    if (k > 0) dfs(root->right, k);
  }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
// @lc code=end
